1. Field of the Invention
The present invention relates to networking technology. More particularly, the present invention relates to providing load sharing and redundancy in a network through a master router and a slave router having a shared set of interfaces in a single device.
2. Description of the Related Art
Networks are commonly used by organizations for a variety of purposes. For instance, through the use of networks, resources such as programs and data may be shared by users of the network. In addition, a computer network can serve as a powerful communication medium among widely separated users.
Communication among hosts and users of a network is often facilitated through connection to one or more routers. As shown in FIG. 1, a host 112 normally resides on a network segment 114 that enables its network entities to communicate with other entities or networks. Note that the host 112 need not directly connect to the entities or networks with which it communicates. For example, as shown in FIG. 1, the host 112 may be connected through a router R1116. The router R1116 may, in turn, connect one or more other routers such as router R2118 with selected entities or networks.
Now, suppose that the host 112 wishes to send a message to a corresponding node 120. A message from the host 112 is then packetized and forwarded through the appropriate routers and to the corresponding node 120, as indicated by dotted line xe2x80x9cpacket from hostxe2x80x9d 122, according to a standard protocol. If the corresponding node 120 wishes to send a message to the host 112xe2x80x94whether in reply to a message from the host 112 or for any other reasonxe2x80x94it addresses that message to the IP address of the host 112 on the network segment 114. The packets of that message are then forwarded to router R1116 and ultimately to the host 112 as indicated by dotted line xe2x80x9cpacket to hostxe2x80x9d 124.
As described above, packets sent to and from the host 112 are forwarded via the router R1116. As shown, the router R1116 is the only route to and from the host 112. Thus, if the router R1116 fails, communication with the host 112 becomes impossible. Accordingly, the reliability of the network as well as the routers in the network is of utmost importance.
As networks become a critical resource in many organizations, it is important that the networks are reliable. One way of achieving reliability is through redundancy. As described above, a single router failure may prevent communication to and from each host and user connected to the router. In many networks, it is common to provide redundancy through the use of multiple routers such that a backup router functions in the event of failure of a primary router. However, when the primary router fails, there is typically a xe2x80x9cswitchover timexe2x80x9d that is required for the backup router to take over the functions of the primary router. As a result, such attempts to provide redundancy in switches suffer from a large switchover time. Accordingly, it would be beneficial if such redundancy could be provided with a reduction in the switchover time from a non-functional to a functional router.
In addition to reliability, it is often desirable to improve performance within a given network. In order to achieve this improvement, load sharing is often preferable. For instance, various users of a network may have a higher traffic level than other users of the network. It would therefore be desirable if performance could be achieved through the distribution of traffic among multiple routers.
In view of the above, it would be desirable if a redundancy and load sharing scheme could be implemented to reduce the switchover time upon failure of a router while implementing a load sharing scheme among multiple routers operating in a single device.
An invention is described herein that provides load sharing and redundancy in a network. This is accomplished, according to one embodiment, through the use of a master router and a slave router operating in the same chassis and having a shared set of interfaces. Prior to failure of the master router, the master router communicates shared state information to the slave router. In addition, the slave router operates in xe2x80x9cstandby modexe2x80x9d to obtain information from the shared set of interfaces. In this manner, the switchover time required to switch from the master router to the slave router upon failure of the master router is significantly reduced.
According to one aspect of the invention, a default gateway is associated with both the master router and the slave router. This is accomplished by assigning a shared IP address and a shared MAC address to both a first router and a second router so that the shared IP and MAC addresses are shared between the first router and the second router. Additionally, a first MAC address is assigned to the first router and a second MAC address is assigned to the second router. The default gateway is configured on the hosts such that a default gateway IP address is associated with the shared IP address. The shared IP and MAC addresses are associated with one of the routers (e.g., the first router or master router). When the master fails, the slave takes over both the shared IP address and the shared MAC address.
In order to route traffic, there are three layers of protocol: a physical layer, a data link layer, and a network layer. The data link layer is often referred to as xe2x80x9clayer 2xe2x80x9d while the network layer is often referred to as xe2x80x9clayer 3.xe2x80x9d The responsibility of the data link layer is to transmit chunks of information across a link. The responsibility of the network layer is to enable systems in the network to communicate with each other. Thus, the network layer finds a path or xe2x80x9cshortcutxe2x80x9d through a series of connected nodes that must forward packets in the specified direction.
According to another aspect, the master and the slave each includes a switching processor to switch packets in hardware and a routing processor to enable packets to be routed in software. The switching processor is adapted for running a layer 2 protocol (e.g., spanning tree) and the routing processor is adapted for running a layer 3 routing protocol. In addition, the master and the slave each maintains its own forwarding data. More particularly, the master and the slave each maintain a layer 2 database associated with the layer 2 protocol and a routing table associated with the layer 3 routing protocol. Both the master and the slave independently run its own layer 3 routing protocol and maintain its own routing table. However, only the master runs the layer 2 protocol. More particularly, the master saves the layer 2 protocol information in a layer 2 protocol database (e.g., spanning tree database) and sends layer 2 protocol updates to the slave so that it may similarly store the layer 2 protocol updates in its own layer 2 protocol database. When the master fails, the slave then runs the layer 2 protocol and accesses its own layer 2 protocol database. Since the slave maintains its own layer 2 protocol database and layer 3 routing table, switchover time upon failure of the master is minimized.
According to another aspect, prior to failure of the master, the slave receives updates from the master in order to synchronize operation of the two routers. For instance, the master maintains the hardware information for both the master and the slave. Therefore, in addition to sending layer 2 protocol updates, the master also sends other information related to the hardware shared by the two routers. As one example, multicast group membership for the shared ports is sent by the master to the slave. As another example, hardware information such as temperature and information related to the power supply is sent by the master to the slave.
According to yet another aspect, the master and the slave each include a forwarding engine in addition to the routing processor and the switching processor. The forwarding engines are adapted for forwarding packets in hardware and therefore increase the speed with which packets are forwarded. Each forwarding engine has an associated set of forwarding engine tables. More particularly, each forwarding engine includes a layer 2 table associating each destination MAC address with a port and router. Thus, if a packet cannot be forwarded in hardware or it is undesirable to forward the packet in hardware, the packet is forwarded by the router specified in the layer 2 table. In addition, a layer 3 shortcut table stores shortcuts (i.e., layer 3 forwarding information) for a path from a particular source IP address to a particular destination IP address. When a router forwards a packet, a shortcut is created and entered in the layer 3 shortcut table. Packets may then be forwarded by the forwarding engine for this particular path.
According to another aspect, the slave operates to update its forwarding tables during standby mode as well as upon failure of the master. In order for the slave to forward a packet, the layer 2 table of the slave""s forwarding engine must contain an entry associating the desired destination MAC address with the slave router. Moreover, for the forwarding engine (i.e., hardware) of the slave to forward a packet, there must be an entry for the particular path from the source IP address to the destination IP address. Thus, prior to failure of the master, the slave""s forwarding engine observes packets at the shared interfaces to obtain information from the packet header to establish shortcuts. For instance, the slave may obtain a shortcut established by the master from the packet header. The slave then updates its layer 2 and layer 3 tables with an appropriate entry as necessary.
Upon failure of the master router, the slave modifies its forwarding engine tables to enable packets to be forwarded by the slave. At a minimum, in order to forward packets in software, the slave""s layer 2 table is modified to associate destination MAC addresses with the slave rather than the master. In addition, in order for a packet to be forwarded via the forwarding engine (i.e., hardware) of the slave, an entry for the specific path is identified in the slave""s layer 3 table. Thus, if an entry exists in the slave""s layer 3 table for the flow (e.g., path from source to destination) as provided in the packet header, the packet may be forwarded by the forwarding engine. Even if the entry in the slave""s layer 3 table for that particular flow is not modified by the slave, packets may be forwarded using information in the current entry using the shortcut established by the master (e.g., with the source MAC address identifying the master). However, it is desirable to forward packets with the correct source MAC address (e.g., the MAC address of the slave). According to one embodiment, since the master and the slave routers may potentially arrive at different routing decisions and therefore different shortcuts, the shortcuts established by the master are invalidated. In order to invalidate these shortcuts, they are removed from the slave""s layer 3 shortcut table. However, if all shortcuts are removed simultaneously, a large number of packets will need to be forwarded in software. Therefore, entries in the slave""s layer 3 shortcut table are selected and removed gradually. For example, the entries may be removed according to port number or other criteria. Once a packet is forwarded by the slave router in software, a correct entry is created and entered in the slave""s shortcut table. Packets may then be forwarded by the slave with a current shortcut as well as correct source MAC address. Thus, since the slave maintains its own forwarding engine tables, packets may be forwarded with a minimum delay time.
According to another aspect, the configuration of the master and the slave is synchronized. There are three categories of information that may be configured for each router. First, there is information that must be the same for both routers. Second, there is information that must be different for both routers. Third, there is information that can be different but is recommended to be the same for both routers. Thus, the same configuration file may be maintained on both the master and the slave to enable the routers to be synchronized with these three categories of information.